package com.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author zhongyi_yang
 */
public class InsertSort {
	/**
	 * 插入排序
	 *
	 * @param dataWraps
	 */
	public static void insertSort(DataWrap[] dataWraps) {
		System.out.println("开始排序：\n");
		int arrayLength = dataWraps.length;
		for (int i = 1; i < arrayLength; i++) {
			// 当整体后移时，保证dataWraps[i]的值不会丢失
			DataWrap tmpDataWrap = dataWraps[i];
			// i索引处的值已经比前面的所有值都大，表明已经有序，无须插入
			// （i-1索引之前的数据已经有序，i-1索引处元素的值就是最大值）
			if (dataWraps[i].compareTo(dataWraps[i - 1]) < 0) {
				int j = i - 1;
				// 整体后移一格
				for (; j >= 0 && dataWraps[j].compareTo(tmpDataWrap) > 0; j--) {
					dataWraps[j + 1] = dataWraps[j];
				}
				// 最后将tmpDataWrap的值插入合适位置
				dataWraps[j + 1] = tmpDataWrap;
			}
			System.out.println(Arrays.toString(dataWraps));
		}
	}

	public static void main(String[] args) {
		DataWrap dataWrap[] = {new DataWrap(9, ""), new DataWrap(-16, ""),
				new DataWrap(21, "*"), new DataWrap(23, ""),
				new DataWrap(-30, ""), new DataWrap(-49, ""),
				new DataWrap(21, ""), new DataWrap(30, "*"),
				new DataWrap(30, "")};
		System.out.println("排序前：" + Arrays.toString(dataWrap));
		insertSort(dataWrap);
		System.out.println("排序后：" + Arrays.toString(dataWrap));
	}
}
